//#include <iostream>
//#include <vector>
//using namespace std;
//
//const int N = 2e6 + 10;
//vector<int> a(N);
//
//int main()
//{
//	int m, n;
//	cin >> m >> n;
//	int i = 0;
//	for (int i = 1; i <= m; i++)
//	{
//		cin >> a[i];
//	}
//	while (n--)
//	{
//		int b;
//		cin >> b;
//		cout << a[b] << endl;
//	}
//	
//	return 0;
// } 



//#include <iostream>
//#include <vector>
//using namespace std;
//
//const int N = 1e5 + 10;
//vector<int> a[N];
//
//int main()
//{
//	int op, i, j, k, m, n;	
//	cin >> m >> n;
//	
//	while (n--)
//	{
//		cin >> op >> i >> j;
//		if (op == 1)
//		{
//			cin >> k;
//			if (a[i].size() <= j)
//			{
//				a[i].resize(j + 1);
//			}
//			a[i][j] = k;
//		}
//		else
//		{
//			cout << a[i][j] << endl;
//		}
//	}
//	
//	return 0;
//}



//#include <iostream>
//#include <vector>
//using namespace std;
//
//const int N = 1e4 + 10;
//vector<int> nums(N);
//
//int main()
//{
//	int n;
//	int i = 1;
//	int sum = 0;
//	while (cin >> n)
//	{
//		nums[i] = n;
//		if (n == 0)
//		{
//			sum++;
//		}
//		i++;
//	}
//	
//	while (sum--)
//	{
//		for (int j = 1; j <= nums.size(); j++)
//		{
//			if (nums[j] == 0)
//			{
//				for (int k = j; j <= nums.size(); j++)
//				{
//					nums[k] = nums[k + 1];
//				}
//				nums[nums.size()] = 0;
//				break;
//			}
//		}
//	}
//	
//	int flag = 0;
//	for (auto e: nums)
//	{
//		if (flag == 0)
//		{
//			cout << nums[e];
//		}
//		else
//		{
//			cout << "," << nums[e];
//		}
//		flag++;
//	}
//	
//	return 0;
//}
//class Solution {
//public:
//    void moveZeroes(vector<int>& nums) {
//        for (int i = 0, cur = -1; i < nums.size(); i++)
//        {
//            if (nums[i])
//            {
//                swap(nums[++cur], nums[i]);
//            }
//        }
//    }
//};



class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = -1, right = nums.size(), cur = 0;
        while (cur < right)
        {
            if (nums[cur] == 0)
            {
                swap(nums[++left], nums[cur++]);
            }
            else if (nums[cur] == 1)
            {
                cur++;
            }
            else 
            {
                swap(nums[--right], nums[cur]);
            }
        }
    }
};
